This invention relates to data processing methods, and more particularly to a method of reduction of Fibonacci p-codes to minimal form and to a device for implementing this method.
The invention is applicable to many fields of computer engineering, including special-purpose digital computers, digital monitoring/diagnostic apparatus for complex automatic systems, means to provide for fidelity of data readout in digital measuring systems and apparatus, and means to provide for error control and failure diagnostics in digital data processing systems.
It is known that natural, fractional and negative numbers can be represented in Fibonacci p-codes which are obtained as a result of generalization of a conventional binary notation. Fibonacci binary number systems are available which are based on Fibonacci p-codes (cf. A.P. Stakhov, The Use of Natural Redundancy of Fibonacci Number Systems for Error Control of Computing Systems. Automation and Computing Machinery, No. 6, 1975 in Russian).
Generalized Fibonaccni numbers of Fibonacci p-numbers are called numbers .phi..sub..rho. (l) which are determined, with p.gtoreq.0, from the following recurrence relation:
______________________________________ 0 when l &gt; 0; .phi..sub.p (l) = 1 when l = 0; .phi..sub.p (l - 1) + .phi..sub.p (l - p - 1) when l &lt; 0. ______________________________________
By a Fibonacci p-code of a natural number N is meant the representation of that number in the form of the following sum: ##EQU1## where n is the code length,
.phi..sub.p (l) is the Fibonacci p-number according to (1), and PA1 a.sub.1 is a bit (0 or 1) in the lth place of the Fibonacci p-code. PA1 Qq.sub..rho. is the value according to (5), and PA1 a.sub.1 is a bit (0 or 1) in the lth place of the code.
With a given integer p.gtoreq.0, there exist, for some natural N, unique non-negative integers i and r which give EQU N=.phi..sub.p (p+i)+r (3) EQU 0.ltoreq.r .phi. .sub.p (i) (4)
When p=0, the Fibonacci p-codes assume their values which are in coincidence with those of a conventional binary code, and when p=.infin., the Fibonacci p-codes represent a unitary code.
The numbers-theory properties of Fibonacci p-numbers are described in the article cited above.
The Fibonacci p-code, according to (2), is characterized, with p&gt;0, by a redundancy, as compared to a conventional binary code (p=0). This means that each natural number N can be represented by several Fibonacci p-codes. For example, number 20, with p=1, can be represented by the following Fibonacci 1-codes:
______________________________________ Digit weight 21 13 8 5 3 2 1 1 ______________________________________ Fibo- 0 1 0 1 0 1 0 0 nacci 0 1 0 1 0 0 1 1 = 20 1-code 0 1 0 0 1 1 1 1 0 0 1 1 1 1 1 1 ______________________________________
Various Fibonacci p-codes of the same natural number N can be obtained with the aid of convolution and devolution operations performed on bits.
By convolution of the lth binary zero (a.sub.1 =0) and the (l-1)th, (l-p-1)th binary ones (a.sub.1-1 =a.sub.1-p-1) of a Fibonacci p-code of a natural number N is meant an operation in which the values of the lth, (l-1)th and (l-p-1)th digits are substituted by their negations which can be expressed as ##EQU2## is the symbol of the convolution operation.
By devolution of the lth binary one (a.sub.1 =1) and binary zeros (l-p) through (l-2p) of a Fibonacci p-code of a natural number N is meant an operation in which the value of the lth digit and the values of digits (l-p) through (l-2p) are substituted by their negations, which can take the form ##EQU3## is the symbol of the devolution operation.
The convolution and/or devolution of bits in a Fibonacci p-code of a natural number N produces a new codeword which represents another Fibonacci p-code of the same number N in accordance with the definition of Fibonacci p-code. Among various forms of a Fibonacci p-code of the same number N, there is one and only one form of the (2) type which contains the minimum number of terms with unitary coefficients.
By the minimal form of a Fibonacci p-code of a number N is meant a Fibonacci p-code produced by sequential factorization, performed according to (3) and (4), of this number N and all remainders that appear in the course of the factorization until the last remainder becomes equal to zero.
Fractional numbers D can also be represented in Fibonacci p-codes. In the case of n-digit encoding of factorial numbers D in a Fibonacci p-code, the weight of the lth digit of an n-digit Fibonacci p-code of a proper fraction is given by the following recurrence relation: ##EQU4## where l.ltoreq.n.
With a certain integer p.gtoreq.0, any proper fraction D has a unique representation, as follows: EQU D=q.sub.p (p+i)+d, (6)
where EQU 0.ltoreq.d&lt;q.sub.p (i). (7)
By a Fibonacci p-code of a proper fraction D is meant the representation of the fraction in the form of the following sum: ##EQU5## where n is the code length,
Note that (6) is solved accurate to q.sub.p (0) in the case of any proper fraction D.
By the minimal form of a Fibonacci p-code of a proper fraction D is meant the form of the (6) type, obtained by sequential factorization of the fraction and all accompanying remainders, performed in accordance with (6) and (7), until the last remainder becomes a value less than q.sub.p (0).
The minimal forms of the Fibonacci p-codes of proper fractions possess all properties of the minimal forms of the Fibonacci p-codes of natural numbers.
Encoding negative numbers in a Fibonacci p-code is carried out using the concept of Fibonacci inverse and additional p-codes. The following relations exist to associate Fibonacci inverse and additional p-codes of natural numbers (N and N.sub.2) and fractional numbers (D and D.sub.1) with Fibonacci straight p-codes of numbers (N and D): EQU N+N=.phi..sub.p (n)-1, EQU N+N.sub.1 =.phi..sub.p (n), EQU N+1=N.sub.1, (9) EQU D+D=1-(1/.phi..sub.p.sup.(n)), EQU D+D.sub.1 =1, EQU D+(1/.phi..sub.p (n))=D.sub.1.
To obtain a Fibonacci inverse p-code of the number N or D from its Fibonacci straight p-code of some N or D, it is sufficient to replace binary coefficients a.sub.2 of the appropriate Fibonacci straight p-codes by their negations.
All basic arithmetic operations such as addition, multiplication and division of integers and fractional numbers can be performed on the minimal form Fibonacci p-codes of the numbers. Also, the following operations are possible: translation of a k-ary position code to a Fibonacci p-code; translation of a Fibonacci p-code to an inverse code; number comparison; counting; and subtraction of ones.